In computer network systems, data is often encapsulated into data messages and transmitted among various entities of the system. A sending entity, for example, may formulate one or more data messages and transmit them across the network for receipt by a receiving entity. The receiving entity captures the data messages and retrieves the data. During transmission, however, errors can be introduced into the data. Accordingly, error control has become an integral part of computer network systems. One of the primary methods to control data transmission errors is known as error detection. With error detection, a receiving entity examines captured data messages to determine whether an error exists. If so, the receiving entity typically discards the data and requests its re-transmission.
One of the more well-known error detection techniques is to calculate and append a checksum valve to each data message. Typically, an agreed-upon algorithm (e.g., a parity check, cyclic redundancy check, hashing function, summation of the number of bits in the packet equal to 1, summation of the numerical values represented by the data, etc.) is applied to the contents of the message prior to its transmission so as to generate a corresponding checksum. The generated checksum is then appended to the data message by the sending entity and the message is transmitted across the network. Upon receipt of the message, the receiving entity applies the same, agreed-upon algorithm to the contents of the message and determines whether its calculation of the checksum matches the checksum contained in the message. If so, the receiving entity concludes that no errors were introduced into the message during its transmission and, therefore, continues processing the data. If the two values do not match, the receiving entity assumes that errors are present in the data and the message is typically discarded.
FIG. 1 is a block diagram of a conventional network data message 100. Message 100, which corresponds to the well-known Transmission Control Protocol (TCP), includes a plurality of fields, including a source port field 102, a destination port field 104, a sequence number (SEQ. NO.) field 106, an acknowledgment number (ACK. NO.) field 108, a header length field 110, a window size field 112, a 16-bit checksum field 114, a pointer (PTR.) field 116, an options field 118 and a variable length data field 120 containing the contents of the message being transmitted. To calculate the checksum value pursuant to the TCP protocol, the checksum field 114 is initially set to zero and the data field 120 is padded with an additional zero byte if its length is an odd number. Next, the sending entity adds up all of the 16-bit portions of the message 100 in 1's complement and then the 1's complement of the sum is taken. In other words, all of the 16-bit portions of the message 100 are summed and the carry over values are added back into the sum. The 16-bit result is loaded into the checksum field 114 and the message 100 is transmitted across the network.
Checksum calculations can either be performed in software by the sending entity's central processor unit (CPU) or in a hardware circuit designed to calculate checksums. Several hardware circuits are known for calculating checksums. In a first checksum generation circuit, two 16-bit registers are used with an adder circuit. In operation, the first register is zeroed and the first 16-bit word of the message 100 is fetched into the second register. The two registers are then added together and result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 16-bit word of the message 100, which is processed in the same manner. After the last 16-bit word has been processed and the carry bit added back to the first register, the first register will contain the checksum value for loading into the checksum field 114.
In another known checksum generation circuit, two 32-bit registers and a corresponding adder circuit are used. Here, the first register is zeroed and the first 32-bits of the message 100 are fetched into the second register. The two registers are then added together and the result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 32-bit segment of the message 100, which is processed in the same manner. After the last 32-bit segment of the message 100 has been processed and the carry bit added to the first register, the low order 16 bits of the register are added to the high order 16 bits and the result loaded into the low order 16 bits of the first register. The carry bit from this last addition is then added back to the low order 16 bits, which represent the final checksum.
U.S. Pat. No. 5,663,952 entitled CHECKSUM GENERATION CIRCUIT AND METHOD to Gentry, Jr., is directed to a checksum generation circuit using two 16-bit adder circuits to generate checksums on a 32-bit data stream. Here, the data stream is split into two 16-bit words and each adder circuit processes a respective 16-bit segment. Each adder circuit also adds back the carry bit for each add cycle and stores the result in a corresponding 16-bit register. After the last 32-bit segment has been processed, three additional steps are performed to obtain the final 16-bit checksum value. First, the 16-bit results produced by each adder circuit are added together along with the last remaining carry bit from the first adder circuit. Second, the last remaining carry bit from the second adder circuit is added back. Third, any carry bit resulting from the second step is added back in, thereby generating the checksum value. The final 16-bit checksum may then be loaded into the respective message.
By operating on two 16-bit words in parallel, the checksum generator of the '952 patent purportedly speeds up the calculation of checksums. It nonetheless has several disadvantages. First, each addition step creates a resulting carry bit. This carry bit, moreover, must be added back in with the next addition step. Furthermore, the creation of any carry bit during the final processing must also be added back in to the final sum. Since most processors typically handle additions sequentially, the adding back of each carry bit requires an additional step consuming processor resources and time. Accordingly, a need has arisen to develop a checksum generator which can operate more efficiently.